Cette activité propose de découvrir les parcours de graphe (en largeur et en profondeur) ainsi que l'algorithme de recherche de plus court chemin dans le cas particulier des labyrinthes rectangulaires. Une première partie algorithmique permet de mettre en place l'algorithme de Dijkstra progressivement au travers d'exercices insistant sur des points clés. la seconde partie propose d'implémenter cet algorithme en Python en réutilisant une activité précédente de modélisation des labyrinthes en programmation objet. Enfin la troisième partie s'intéresse à la visualisation des chemins solutions calculés en 2D (Python) puis en 3D (JavaScript).
La première partie fait intervenir des notions algorithmiques avancées. Même si on fait l'économie d'aborder ici la notion de graphe plus générale, il est nécessaire que les élèves aient déjà mis en place des algorithmes plus simple afin d'être familiarisé avec cette démarche. Il est également nécessaire d'avoir traité l'activité précédente sur la modélisation de labyrinthes.
La deuxième partie nécessite d'avoir découvert la programmation objet en Python. La manipulation de tableaux pourra introduire des problèmes de bords. La modélisation des chemins comme une liste de coordonnées pourrait nécessiter le recours à des affectations multiples et à des itérations sur plusieurs variables :
la troisième partie demande peu de connaissances préalables. La visualisation 2D des labyrinthes utilise superficiellement la librairie matplotlib pour tracer des segments. La visualisation 3D nécessite d'être familiarisé avec la syntaxe des commandes de base en JavaScript.
- Algorithmique avancée, parcours en largeur et en profondeur.
- Programmation objet, définition d'une classe, attributs et méthodes.
- Modélisation d'une situation, choix de représentation
- Utilisation de listes, piles, tableaux et dictionnaires
- Réalisation de solutions algorithmiques dans un contexte pratique
- Encourager une réflexion préalable déconnectée
Extraits du BO :
| Contenus | Capacités attendues |
|---|---|
| Algorithmes sur les graphes | Parcourir un graphe en profondeur, en largeur. Repérer un cycle. Chercher un chemin. |
| Listes, piles, files. Dictionnaires, index et clé. | Choisir une structure de données adaptée à la situation à modéliser. |
| Vocabulaire de la programmation objet :classes, attributs, méthodes, objets. | Écrire la définition d’une classe. Accéder aux attributs et méthodes d’une classe |
| Mise au point des programmes. Gestion des bugs. | Dans la pratique de laprogrammation, savoir répondre aux causes typiques de bugs : effets de bord non désirés, débordements dans les tableaux, instruction conditionnelle non exhaustive... |
| Utilisation de bibliothèques | Utiliser la documentation d’une bibliothèque. |
La première partie propose au travers d'exercices de produire des algorithmes qu'il faudra modifier et étoffer jusqu'à décrire un algorithme de recherche de plus court chemin. La présence de mini-labyrinthes interactifs permet de traiter cette partie algorithmique en salle informatique ou avec des tablette en classe. Les élèves devront réfléchir seuls ou en binômes aux algorithmes à produire à partir de méthodes trouvées empiriquement pour parcourir les labyrinthes interactifs. Les solutions trouvées seront discutées avec la classe entre chaque exercice pour avancer ensemble. Ca sera aussi l'occasion d'introduire les notions de file et de pile. On peut éventuellement commencer à réfléchir à des structures de données adaptées. Idéalement, cette partie devrait prendre une heure, mais peut empiéter sur la séance suivante.
La deuxième partie se déroule en salle informatique. Les élèves peuvent travailler seuls ou en binômes. Commencer la séance en rappelant l'algorithme décrit à la séance précédente. Les exercices découpent l'algorithme principal en plusieurs méthodes permettant de gérer l'initialisation des attributs, la recherche des voisins, l'actualisation des distances et le choix de la cellule suivante. Encourager les élèves à utiliser la méthode print() pour visualiser les étapes de leurs parcours. Mettre en garde sur les boucles infinies qui pourraient vite devenir pénibles pour la séance. Proposer éventuellement de placer un compteur et l'instruction break.
La troisième partie peut faire suite à la deuxième lors d'une séance supplémentaire ou dés la réalisation des objectifs atteints par l'élève. Il n'y a pas de difficulté particulière. Il s'agit principalement d'adapter et de modifier les scripts de l'activité précédente.
- Un environnement de développement Python avec les librairies matplotlib, random et éventuellement numpy.
- Un navigateur récent (Firefox, Chrome, Edge, pas testé sur Safari). A noter que la scène 3D tourne (beaucoup) mieux sous Chrome... :/
- Un éditeur de texte basique (Notepad++, Scite, Bracket, Sublime Text, etc.) pour la partie JavaScript
-
Des pondération sur les cellules d'un labyrinthe peuvent être utilisées pour représenter des hauteurs et donc des cellules plus longues à parcourir.
-
Adapter la recherche de plus court chemin à des labyrinthes en 3D
- Adapter l'algorithme à des labyrinthes de formes différentes (circulaires, hexagonaux,...)
-
Généraliser l'algorithme de Dijkstra a des graphes plus généraux (pondérés, orientés, etc.).
-
Aborder le problème de recherche de chemins dans un contexte différent où on connaît la direction de l'arrivée (algorithme A*)
